#include <stdio.h>
#include <string.h>

int wildcard_helper(const char *target, int i, int tlen, const char *pattern, int j, int plen)
{
    int i2 = i, j2 = j;
    while (i2 < tlen && j2 < plen && target[i2] == pattern[j2]) {
        i2++;
        j2++;
    }
    if (j2 == plen) {
        return (i2 == tlen) ? 1 : 0;
    }
    if (pattern[j2] != '*') {
        return 0;
    } else {
        int k, f = 0;
        /* XXX: was '<'. since j may equals plen, make sure i may also equals tlen. */
        for (k = i2; k <= tlen; k++) {
            if (wildcard_helper(target, k, tlen, pattern, j2+1, plen)) { /* recursion */
                f = 1;
                break;
            }
        }
        return f;
    }
}

int wildcard(const char *target, const char *pattern)
{
    return wildcard_helper(target, 0, strlen(target), pattern, 0, strlen(pattern));
}

int main()
{
    const char *target = "abcba";
    const char *pattern = "*a*c*a**";
    int f = wildcard(target, pattern);
    printf("%s matches %s ? %d\n", target, pattern, f);
    return 0;
}
